package LeetCode;

public class LC_322_CoinChange {

    public static void main(String[] args) {

    }

    static class Solution {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount + 1];
            for (int i = 1; i <= amount; i++) {
                dp[i] = 0x7fffffff;
                for (int coin : coins)
                    if (i >= coin && dp[i - coin] != 0x7fffffff)
                        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
            return dp[amount] == 0x7fffffff ? -1 : dp[amount];
        }
    }

    static class Solution_2 {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount + 1];
            for (int i = 1; i <= amount; i++) dp[i] = 0x7fff_fffe;
            for (int coin : coins)
                for (int i = coin; i <= amount; i++)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            return dp[amount] == 0x7fff_fffe ? -1 : dp[amount];
        }
    }

}